package cn.com.ninng;

/**
 * 搜索插入位置
 *给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * @author liulekang
 * @createdate 2021/7/28
 */
public class Problem35 {

    public static void main(String[] args) {
        System.out.println(searchInsert(new int[]{1,3,5,6},5));
    }


    public static int searchInsert(int[] nums, int target) {
        //看到是排序数组和要求O(log n)，感觉应该使用二分查找

        int i = 0;
        int j = nums.length-1;
        while (i <= j){
            int index = (j-i)/2 + i;
            if (nums[index] > target) {
                //大于目标值，移动右边界
                j = index -1;
            } else if (nums[index] < target){
                //小于目标值，移动左边界
                i = index + 1 ;
            }else {
                //相等，代表找到了
                return index;
            }
        }
        return i;
    }



}
